package com.xk._02算法篇._03graph.graph;

import com.xk._02算法篇._03graph.GenericUnionFind;
import com.xk._02算法篇._03graph.MinHeap;

import java.util.*;

/**
 * @description:
 * @author: xu
 * @date: 2022/10/5 20:28
 */
public class ListGraph<V, E> extends Graph<V, E>{
    private Map<V, Vertex<V,E>> vertices = new HashMap<>();
    private Set<Edge<V, E>> edges = new HashSet<>();
    private Comparator<Edge<V, E>> edgeComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
        return weightManager.compare(e1.weight, e2.weight);
    };

    public ListGraph(WeightManager<E> weightManager) {
        super(weightManager);
    }
    public ListGraph() {}

    // 顶点
    private static class Vertex<V, E> {
        V value;
        Set<Edge<V,E>> inEdges = new HashSet<>();
        Set<Edge<V,E>> outEdges = new HashSet<>();
        Vertex(V value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Vertex)) return false;
            Vertex<?, ?> vertex = (Vertex<?, ?>) o;
            return Objects.equals(value, vertex.value);
        }
        @Override
        public int hashCode() {
            return Objects.hash(value);
        }

        @Override
        public String toString() {
            return value == null ? "null" : value.toString();
        }
    }

    // 边
    private static class Edge<V, E> {
        Vertex<V,E> from;
        Vertex<V,E> to;
        E weight;

        Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this(from, to, null);
        }
        Edge(Vertex<V, E> from, Vertex<V, E> to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        EdgeInfo<V, E> info(){
            return new EdgeInfo<>(from.value, to.value, weight);
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (!(o instanceof Edge)) return false;
            Edge<V, E> edge = (Edge<V, E>) o;
            return Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

    public void print(){
        vertices.forEach((V key, Vertex<V,E> vertex) -> {
            System.out.println(key);
            System.out.println("out: " + vertex.outEdges);
            System.out.println("in : " + vertex.inEdges);
        });
        System.out.println("================================");
        edges.forEach((Edge<V,E> edge) -> {
            System.out.println(edge);
        });
    }

    /**
     * 返回边的数量
     * @return
     */
    @Override
    public int edgesSize() {
        return edges.size();
    }

    /**
     * 返回顶点的数量
     * @return
     */
    @Override
    public int verticsSize() {
        return vertices.size();
    }

    /**
     * 添加顶点
     * @param v
     */
    @Override
    public void  addVertex(V v) {
        if (vertices.containsKey(v)) return;
        vertices.put(v, new Vertex<>(v));
    }

    /**
     * 添加边：无权值
     * @param from
     * @param to
     */
    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to, null);
    }

    /**
     * 添加边：有权值
     * @param from
     * @param to
     * @param weight
     */
    @Override
    public void addEdge(V from, V to, E weight) {
        // 判断 from 、to 顶点是否存在
        Vertex<V, E> fromVertex = vertices.get(from);
        Vertex<V, E> toVertex = vertices.get(to);
        if (fromVertex == null) {
            vertices.put(from, fromVertex = new Vertex<>(from));
        }
        if (toVertex == null) {
            vertices.put(to, toVertex = new Vertex<>(to));
        }
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex, weight);

        if (fromVertex.outEdges.remove(edge)){
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }

    /**
     * 删除顶点
     * @param v
     */
    @Override
    public void removeVertex(V v) {
        Vertex<V, E> vertex = vertices.remove(v);
        if (vertex == null) return;

        // 迭代器
        Iterator<Edge<V, E>> outIterator = vertex.outEdges.iterator();
        while (outIterator.hasNext()) {
            Edge<V, E> edge = outIterator.next();
            edge.to.inEdges.remove(edge);
            // 将当前遍历到的元素edge从集合vertex.outEdges中删除
            outIterator.remove();
            edges.remove(edge);
        }

        Iterator<Edge<V, E>> inIterator = vertex.inEdges.iterator();
        while (inIterator.hasNext()) {
            Edge<V, E> edge = inIterator.next();
            edge.from.outEdges.remove(edge);
            // 将当前遍历到的元素edge从集合vertex.inEdges中删除
            inIterator.remove();
            edges.remove(edge);
        }
    }

    /**
     * 删除边
     * @param from
     * @param to
     */
    @Override
    public void removeEdge(V from, V to) {
        Vertex<V, E> fromVertex = vertices.get(from);
        Vertex<V, E> toVertex = vertices.get(to);
        if (fromVertex == null || toVertex == null) return;
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex);
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
    }

    /*BFS===================================================================================*/
    /**
     * 广度优先遍历
     * @param begin
     */
    @Override
    public void bfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Deque<Vertex<V, E>> queue = new LinkedList<>();
        queue.offer(beginVertex);
        visitedVertices.add(beginVertex);

        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            if (visitor.visit(vertex.value)) return;
            for (Edge<V, E> edge : vertex.outEdges) {
                if (visitedVertices.contains(edge.to)) continue;
                queue.offer(edge.to);
                visitedVertices.add(edge.to);
            }
        }
    }
    /*DFS===================================================================================*/
    /**
     * 深度优先遍历：递归
     * @param begin
     */
    @Override
    public void dfs1(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return;

        dfs1(beginVertex, visitor, new HashSet<>());
    }
    private void dfs1(Vertex<V, E> vertex, VertexVisitor<V> visitor, Set<Vertex<V, E>> visitedVertices) {
        if (visitor.visit(vertex.value)) return;
        visitedVertices.add(vertex);
        for (Edge<V, E> outEdge : vertex.outEdges) {
            if (visitedVertices.contains(outEdge.to)) continue;
            dfs1(outEdge.to, visitor, visitedVertices);
        }
    }
    /**
     * 深度优先遍历：非递归
     * @param begin
     */
    public void dfs(V begin, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        Vertex<V, E> vertex = vertices.get(begin);
        if (vertex == null) return;

        Set<Vertex<V, E>> visitedVertices = new HashSet<>();
        Deque<Vertex<V, E>> stack = new LinkedList<>();

        //先访问起点
        stack.push(vertex);
        visitedVertices.add(vertex);
        if (visitor.visit(vertex.value)) return;

        while (!stack.isEmpty()) {
            Vertex<V, E> pop = stack.pop();

            for (Edge<V, E> outEdge : pop.outEdges) {
                if (visitedVertices.contains(outEdge.to)) continue;
                stack.push(outEdge.from);
                stack.push(outEdge.to);
                visitedVertices.add(outEdge.to);
                if (visitor.visit(outEdge.to.value)) return;
                break;
            }
        }
    }

    /*拓扑排序：卡恩算法===================================================================================*/
    /**
     * 拓扑排序：卡恩算法
     * @return
     */
    @Override
    public List<V> topologicalSort() {
        List<V> list = new ArrayList<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        Map<Vertex<V, E>, Integer> ins = new HashMap<>();

        // 初始化（将入度为0的节点都放入队列）
        vertices.forEach((V v, Vertex<V, E> vertex) -> {
            int inSize = vertex.inEdges.size();
            if (inSize == 0) queue.offer(vertex);
            else ins.put(vertex, inSize);
        });

        while (!queue.isEmpty()) {
            Vertex<V, E> vertex = queue.poll();
            // 放入返回结果中
            list.add(vertex.value);

            for (Edge<V, E> outEdge : vertex.outEdges) {
                int in = ins.get(outEdge.to) - 1;
                if (in == 0) queue.offer(outEdge.to);
                else ins.put(outEdge.to, in);
            }
        }
        return list;
    }

    /*最小生成树===================================================================================*/
    /**
     * 最小生成树：默认无向图
     * @return
     */
    @Override
    public Set<EdgeInfo<V, E>> mst() {
        return Math.random() > 0.5 ? mst_prim() : mst_kruskal();
    }
    /**
     * 最小生成树：prim算法
     * @return
     */
    private Set<EdgeInfo<V, E>> mst_prim() {
        Iterator<Vertex<V, E>> it = vertices.values().iterator();
        if (!it.hasNext()) return null;
        Vertex<V, E> vertex = it.next();
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        Set<Vertex<V, E>> addedVertices = new HashSet<>();
        addedVertices.add(vertex);

        MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges, edgeComparator);

        while (!heap.isEmpty() && verticsSize() > addedVertices.size()) {
            Edge<V, E> edge = heap.remove();
            if (addedVertices.contains(edge.to)) continue;
            edgeInfos.add(edge.info());
            addedVertices.add(edge.to);
            heap.addAll(edge.to.outEdges);
        }
        return edgeInfos;
    }
    /**
     * 最小生成树：kruskal算法
     * @return
     */
    private Set<EdgeInfo<V, E>> mst_kruskal(){
        int edgeSize = verticsSize() - 1;
        if (edgeSize < 2) return null;

        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        MinHeap<Edge<V,E>> heap = new MinHeap<>(edges, edgeComparator);

        //并查集：用于环的判断
        GenericUnionFind<Vertex<V, E>> unionFind = new GenericUnionFind<>(vertices.values());

        while (!heap.isEmpty() && edgeInfos.size() < edgeSize) {
            Edge<V, E> edge = heap.remove();
            if (unionFind.isSame(edge.from, edge.to)) continue;
            edgeInfos.add(edge.info());
            unionFind.union(edge.from, edge.to);
        }
        return edgeInfos;
    }

    /**
     * 单源最短路径
     * @param begin
     * @return
     */
    @Override
    public Map<V, PathInfo<V, E>> shortestPath(V begin) {
        return dijkstra(begin);
    }
    /*单源最短路径：Dijkstra========================================================================*/
    /**
     * 单源最短路径：Dijkstra实现，迪杰斯特拉算法实现
     * @param begin
     * @return
     */
    private Map<V, PathInfo<V, E>> dijkstra(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;

        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        paths.put(beginVertex, new PathInfo<>(weightManager.zero()));
        //初始化paths
        //for (Edge<V, E> outEdge : beginVertex.outEdges) {
        //    PathInfo<V, E> pathInfo = new PathInfo<>();
        //    pathInfo.setWeight(outEdge.weight);
        //    pathInfo.edgeInfos.add(outEdge.info());
        //    paths.put(outEdge.to, pathInfo);
        //}

        while (!paths.isEmpty()) {
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getShortestPath(paths);
            // minVertex离开桌面
            Vertex<V, E> minVertex = minEntry.getKey();
            PathInfo<V, E> minPath = minEntry.getValue();
            selectedPaths.put(minVertex.value, minPath);
            paths.remove(minVertex);
            // 对它的 minVertex 的 outEdges 进行松弛操作
            for (Edge<V, E> edge : minVertex.outEdges) {
                // 如果edge.to已经离开桌面，就没必要进行松弛操作
                if (selectedPaths.containsKey(edge.to.value)) continue;
                relaxForDijkstra(edge, minPath, paths);
            }
        }
        selectedPaths.remove(begin);
        return selectedPaths;
    }
    /**
     * 从paths中挑一个最小的路径出来
     * @param paths
     * @return
     */
    private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getShortestPath(Map<Vertex<V, E>, PathInfo<V, E>> paths){
        Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> iterator = paths.entrySet().iterator();
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = iterator.next();
        while (iterator.hasNext()){
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> entry = iterator.next();
            if (weightManager.compare(entry.getValue().weight, minEntry.getValue().weight) < 0) {
                minEntry = entry;
            }
        }
        return minEntry;
    }
    /**
     * 松弛操作 -- Dijkstra
     * @param edge 需要进行松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths 存放着其他点（对于dijkstra来说，还没有离开桌面的点）的最短路径信息
     */
    private void relaxForDijkstra(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<Vertex<V, E>, PathInfo<V, E>> paths){
        // 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        // 以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to);

        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return;

        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }
        oldPath.setWeight(newWeight);
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());
    }
    /*单源最短路径：Bellman-Ford=====================================================================*/
    /**
     * 单源最短路径：Bellman-Ford实现，贝尔曼-福特算法实现
     * @param begin
     * @return
     */
    private Map<V, PathInfo<V, E>> bellmanFord(V begin) {
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;

        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        selectedPaths.put(begin, new PathInfo<>(weightManager.zero()));

        int count = verticsSize() - 1;
        for (int i = 0; i < count; i++) { // V - 1次
            for (Edge<V, E> edge : edges) {
                PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
                if (fromPath == null) continue;
                relaxForBellmanFord(edge, fromPath, selectedPaths);
            }
        }

        for (Edge<V, E> edge : edges) {
            PathInfo<V, E> fromPath = selectedPaths.get(edge.from.value);
            if (fromPath == null) continue;
            if (relaxForBellmanFord(edge, fromPath, selectedPaths)) {
                throw new RuntimeException("有负权环，无最短路径");
            }
        }
        selectedPaths.remove(begin);
        return selectedPaths;
    }
    /**
     * 松弛操作 -- BellmanFord
     * @param edge 需要进行松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths 存放着其他点（对于dijkstra来说，还没有离开桌面的点）的最短路径信息
     */
    private boolean relaxForBellmanFord(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, PathInfo<V, E>> paths){
        // 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
        E newWeight = weightManager.add(fromPath.weight, edge.weight);
        // 以前的最短路径：beginVertex到edge.to的最短路径
        PathInfo<V, E> oldPath = paths.get(edge.to.value);

        if (oldPath != null && weightManager.compare(newWeight, oldPath.weight) >= 0) return false;

        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to.value, oldPath);
        } else {
            oldPath.edgeInfos.clear();
        }
        oldPath.setWeight(newWeight);
        oldPath.edgeInfos.addAll(fromPath.edgeInfos);
        oldPath.edgeInfos.add(edge.info());
        return true;
    }

    /*多源最短路径===================================================================================*/
    /**
     * 多源最短路径
     * @return
     */
    @Override
    public Map<V, Map<V, PathInfo<V, E>>> shortestPaths() {
        return floyd();
    }
    /**
     * 多源最短路径：floyd，弗洛伊德算法实现
     * @return
     */
    private Map<V, Map<V, PathInfo<V, E>>> floyd(){
        Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();
        // 初始化
        for (Edge<V, E> edge : edges) {
            Map<V, PathInfo<V, E>> map = paths.get(edge.from.value);
            if (map == null) {
                map = new HashMap<>();
                paths.put(edge.from.value, map);
            }
            PathInfo<V, E> pathInfo = new PathInfo<>(edge.weight);
            pathInfo.edgeInfos.add(edge.info());
            map.put(edge.to.value, pathInfo);
        }

        vertices.forEach((V v2, Vertex<V, E> vertex2) -> {
            vertices.forEach((V v1, Vertex<V, E> vertex1) -> {
                vertices.forEach((V v3, Vertex<V, E> vertex3) -> {
                    if (Objects.equals(v1, v2) || Objects.equals(v2, v3) || Objects.equals(v1, v3)) return;

                    // v1 --> v2
                    PathInfo<V, E> path12 = getPathInfo(v1, v2, paths);
                    if (path12 == null) return;
                    // v2 --> v3
                    PathInfo<V, E> path23 = getPathInfo(v2, v3, paths);
                    if (path23 == null) return;
                    // v1 --> v3
                    PathInfo<V, E> path13 = getPathInfo(v1, v3, paths);

                    E newWeight = weightManager.add(path12.weight, path23.weight);
                    if (path13 != null && weightManager.compare(newWeight, path13.weight) >= 0) return;
                    if (path13 == null) {
                        path13 = new PathInfo<>();
                        paths.get(v1).put(v3, path13);
                    } else {
                        path13.edgeInfos.clear();
                    }
                    path13.setWeight(newWeight);
                    path13.edgeInfos.addAll(path12.edgeInfos);
                    path13.edgeInfos.addAll(path23.edgeInfos);
                });
            });
        });
        return paths;
    }
    private PathInfo<V, E> getPathInfo(V from, V to, Map<V, Map<V, PathInfo<V, E>>> paths){
        Map<V, PathInfo<V, E>> map = paths.get(from);
        return map == null ? null : map.get(to);
    }

    ///**
    // * 单源最短路径：Dijkstra实现，迪杰斯特拉算法实现
    // * @param begin
    // * @return
    // */
    //public Map<V, E> shortestPath1(V begin) {
    //    Vertex<V, E> vertex = vertices.get(begin);
    //    if (vertex == null) return null;
    //
    //    Map<V, E> selectedPaths = new HashMap<>();
    //    Map<Vertex<V, E>, E> paths = new HashMap<>();
    //    //初始化paths
    //    for (Edge<V, E> outEdge : vertex.outEdges) {
    //        paths.put(outEdge.to, outEdge.weight);
    //    }
    //
    //    while (!paths.isEmpty() && selectedPaths.size() < verticsSize()){
    //        Map.Entry<Vertex<V, E>, E> minEntry = getShortestPath11(paths);
    //        // minVertex离开桌面
    //        Vertex<V, E> minVertex = minEntry.getKey();
    //        E minPath = minEntry.getValue();
    //        selectedPaths.put(minVertex.value, minPath);
    //        paths.remove(minVertex);
    //        // 对它的 minVertex 的 outEdges 进行松弛操作
    //        for (Edge<V, E> edge : minVertex.outEdges) {
    //            // 如果edge.to已经离开桌面，就没必要进行松弛操作
    //            if (selectedPaths.containsKey(edge.to.value)) continue;
    //
    //            // 新的可选择的最短路径：beginVertex到edge.from的最短路径 + edge.weight
    //            E newWeight = weightManager.add(minPath, edge.weight);
    //            // 以前的最短路径：beginVertex到edge.to的最短路径
    //            E oldWeight = paths.get(edge.to);
    //            if (oldWeight == null || weightManager.compare(newWeight, oldWeight) < 0) {
    //                paths.put(edge.to, newWeight);
    //            }
    //        }
    //    }
    //    selectedPaths.remove(vertex);
    //    return selectedPaths;
    //}
    //
    ///**
    // * 从paths中挑一个最小的路径出来
    // * @param paths
    // * @return
    // */
    //private Map.Entry<Vertex<V, E>, E> getShortestPath11(Map<Vertex<V, E>, E> paths){
    //    Iterator<Map.Entry<Vertex<V, E>, E>> iterator = paths.entrySet().iterator();
    //    Map.Entry<Vertex<V, E>, E> minEntry = iterator.next();
    //    while (iterator.hasNext()){
    //        Map.Entry<Vertex<V, E>, E> entry = iterator.next();
    //        if (weightManager.compare(entry.getValue(), minEntry.getValue()) < 0) {
    //            minEntry = entry;
    //        }
    //    }
    //    return minEntry;
    //}
}